package 剑指offer;

import java.util.*;

public class test{
    public int[] twoSum(int[] numbers, int target) {
        int i = 0, j = numbers.length - 1;
        int[] res = new int[2];
        while (i < j){
            int sum = numbers[i] + numbers[j];
            if(sum > target){
                j--;
            }else if(sum < target){
                i++;
            }else{

                res[0] = i;
                res[1] = j;
                return res;
            }
        }
        return res;
    }
    /*public int pathSum(TreeNode root, int targetSum) {
        Map<Integer,Integer> preSum = new HashMap<>();
        preSum.put(0,1);
        return getSum(root,preSum,targetSum,0);
    }
    public int getSum(TreeNode root, Map<Integer,Integer> preSum,int target,int curSum){
        if(root == null){
            return 0;
        }
        int res = 0;
        curSum += root.val;
        res += preSum.getOrDefault(curSum - target,0);
        preSum.put(curSum, preSum.getOrDefault(curSum, 0) + 1);

        res += getSum(root.left,preSum,target,curSum);
        res += getSum(root.right,preSum,target,curSum);

        preSum.put(curSum,preSum.get(curSum) - 1);
        return res;
    }*/

    /*public int longestCommonSubsequence(String text1, String text2) {
        int[][] arr = new int[text1.length() + 1][text2.length() + 1];
        for(int i = 1; i < arr.length; i++){
            for(int j = 1; j < arr[0].length; j++){
                char s1 = text1.charAt(i - 1), s2 = text2.charAt(j - 1);
                if(s1 == s2){
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                }else{
                    arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
                }
            }
        }
        return arr[arr.length - 1][arr[0].length - 1];
    }*/
    /*public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList();
        for(int i = 0; i < tokens.length; i++){
            String s = tokens[i];
            if(isNumber(s)){
                stack.push(Integer.parseInt(s));
            }else{
                Integer num1 = stack.pop();
                Integer num2 = stack.pop();
                switch (s){
                    case "+":
                        stack.push(num2 + num1);break;
                    case "-":
                        stack.push(num2 - num1);break;
                    case "*":
                        stack.push(num2 * num1);break;
                    case "/":
                        stack.push(num2 / num1);break;
                }
            }
        }
        return stack.pop();
    }
    public boolean isNumber(String num){
        return !(num.equals("+") || num.equals("-") || num.equals("*") || num.equals("/"));
    }*/
    /*public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        dfs(candidates, target, ans, combine, idx + 1);
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }*/

    /*public static void fun(int[] nums,int start,int end){
        if(start >= end){
            return;
        }
        int begin = nums[start],i = start,j = end;
        while (i < j){
            while (i < j && nums[j] >= begin){
                j--;
            }
            while (i < j && nums[i] <= begin){
                i++;
            }
            if(i < j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }

        nums[start] = nums[i];
        nums[i] = begin;

        fun(nums,start,i - 1);
        fun(nums,i + 1,end);
    }*/

}